#include <stdlib.h>
#include <stdio.h>

typedef char DataType;

typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/

// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements);

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item));


//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item));


//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item));


// 可以无需更改本函数的实现
void visit(DataType item);

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x);

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root);
